package com.lmk.dsa.struct.heap;

import com.lmk.dsa.struct.commons.KvNode;

/**
 * 大顶堆
 * @author LaoMake
 * @since 1.0
 */
public class MaxHeap extends AbstractHeap {

    public MaxHeap() {
    }

    public MaxHeap(int capacity) {
        super(capacity);
    }

    public MaxHeap(KvNode[] array) {
        super(array);
    }

    @Override
    protected void siftUp(int index) {
        if(index == 0){
            return;
        }

        int parentIndex = parent(index);
        KvNode child = (KvNode) nodes[index];
        KvNode parent = (KvNode) nodes[parentIndex];

        if(child.key.compareTo(parent.key) > 0){
            swap(index, parentIndex);
            siftUp(parentIndex);
        }
    }

    @Override
    protected void siftDown(int index) {
        if(index < 0 || index >= size){
            return;
        }

        int childIndex = leftChild(index);
        if(childIndex < size){
            KvNode parent = (KvNode) nodes[index];

            KvNode child = (KvNode) nodes[childIndex];
            if(childIndex + 1 < size){
                KvNode rightChild = (KvNode) nodes[childIndex + 1];
                if(rightChild.key.compareTo(child.key) > 0){
                    child = rightChild;
                    childIndex++;
                }
            }

            if(child.key.compareTo(parent.key) > 0){
                swap(childIndex, index);
                siftDown(childIndex);
            }
        }
    }


}
